package dfs;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * GetTheMinSumOfTreePath 找出一颗满二叉树从根节点到叶子节点的最小和，叶子节点，left与right都等于Null
 *
 * @author <a href="zhaoyingling12@163.com">Zhao Simon</a>
 * @description:
 * @date 2021/5/11
 **/
public class GetTheMinSumOfTreePath {
    public static void main(String[] args) {
        TreeNode root = structureTree();
        int min = getTheMinSumOfTreePath(root);
        System.out.println("min ==> " + min);
    }

    public static int getTheMinSumOfTreePath(TreeNode root) {
        Set<TreeNode> visited = new HashSet<>();
        List<Integer> ans = new ArrayList<>();
        dfs(visited, root, 0, ans);
        int min = Integer.MAX_VALUE;
        for (int num : ans) {
            min = Math.min(num, min);
        }
        return min;
    }

    public static void dfs(Set<TreeNode> visited, TreeNode root, int sum, List<Integer> ans) {
        if (root == null) return;
        if (visited.contains(root)) return;
        visited.add(root);
        sum += root.val;
        if (root.left != null) dfs(visited, root.left, sum, ans);
        if (root.right != null) dfs(visited, root.right, sum, ans);
        if (root.left == null && root.right == null) {
            ans.add(sum);
        }
    }

    public static TreeNode structureTree() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(7);
        root.left.right = new TreeNode(1);
        root.right.left = new TreeNode(9);
        root.right.right = new TreeNode(0);
        return root;
    }
}
